package com.demo.data.struct.stack;

import java.util.Stack;

/**
问题描述
输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。
例如序列 1，2，3，4，5 是某栈的压入顺序，序列 4，5，3，2，1是该压栈序列对应的一个弹出序列，但4，3，5，1，2就不可能是该压栈序列的弹出序列。
（注意：这两个序列的长度是相等的）

解题思路
借用一个辅助的栈，遍历压栈顺序，先讲第一个放入栈中，这里是 1，然后判断栈顶元素是不是出栈顺序的第一个元素，这里是 4，很显然 1≠4 ，
所以需要继续压栈，直到相等以后开始出栈。

出栈一个元素，则将出栈顺序向后移动一位，直到不相等，这样循环等压栈顺序遍历完成，如果辅助栈还不为空，说明弹出序列不是该栈的弹出顺序。
 *
 */
public class 栈的压入弹出序列 {

	public static boolean isPopOrder(int[] pushSequence, int[] popSequence) {
		Stack<Integer> s = new Stack<>();
		if(pushSequence.length != popSequence.length){
			return false;
		}
		int count = pushSequence.length;
		for(int pushIndex=0, popIndex=0; pushIndex<count; pushIndex++){
			s.push(pushSequence[pushIndex]);
			while(popIndex<count && !s.isEmpty() && s.peek() == popSequence[popIndex]){
				s.pop();
				popIndex++;
			}
		}
		return s.isEmpty();
	}

	public static void main(String[] args) {
		int[] pushSequence = new int[]{1, 2, 3, 4, 5};
		int[] popSequence = new int[]{4, 5, 3, 2, 1};
		System.out.println(栈的压入弹出序列.isPopOrder(pushSequence, popSequence));
	}

}
